<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1：
            输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3, 找到最多5个0,3个1的子集的大小，
            输出：4
            解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 
            其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。
            {"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3

            题目描述：
            1. 找到最多m个0、n个1的最大子集的长度
            2. 数量超出，或者不是最大子集的数量不在计算之内

        */
        var findMaxForm = function(strs, m, n) {
            // 写一个函数计算字符串的数量
            function countStrNum (strs) {
                // zero和one用来计数
                let one = 0
                let zero = 0
                for (const str of strs) {
                    if (str === '0') zero++
                    else if (str === '1') one++
                }
                return [zero, one]
            }
            // 用来递归调用
            // index remainZero remainOne
            // 结果如何
            function traverseStr (index, remainZero, remainOne) {
                // 到达字符串的长度
                if (index === strs.length) {
                    return 0
                }

                // 不取当前的字符串
                let result = traverseStr(index + 1, remainZero, remainOne)
                // 取当前的字符串
                const [zero, one] = countStrNum(strs[index])
                // 必须比remainZero和remainOne小才能继续递归
                if (zero <= remainZero && one <= remainOne) {
                    // 1+的意思是当前字符串已经取了，要多一个
                    // remainZero - zero表示当前的zero已经放进了背包
                    result = Math.max(result, 1 + traverseStr(index + 1, remainZero - zero, remainOne - one))
                }
                return result
            }
            return traverseStr(0, m, n)
        };
        // console.log(findMaxForm(["10", "0001", "111001", "1", "0"], 5, 3));
        // console.log(findMaxForm(["10","0","1"], 1, 1));
        console.log(findMaxForm(["11","11","0","0","10","1","1","0","11","1","0","111","11111000","0","11","000","1","1","0","00","1","101","001","000","0","00","0011","0","10000"], 90, 60));
    </script>
</body>

</html>